package com.base.dataStructure.Tree;

import lombok.NoArgsConstructor;

/**
 * @Author: hdhao
 * @Create: 2023/4/6 - 20:05
 * @Version: v1.0
 */
//二叉搜索树
public class BSTTree1 {
    //根节点
    BSTNode root;

    /**
     * 查找关键字对应的值
     *
     * @param key
     * @return
     */
    public Object get(int key) {
        return doGet(root, key);
    }

    /**
     * 查找最小关键字对应的值
     *
     * @return
     */
    public Object min() {
        //递归实现
        //return doMin(root);
        return min(root);
    }

    public Object min(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    public Object doMin(BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            //已经找到了最小值
            return node.value;
        }
        return doMin(node.left);
    }

    /**
     * 查找最大关键字对应的值
     *
     * @return
     */
    public Object max() {
        //递归实现
        //return doMax(root);

        //非递归实现
        return max(root);
    }

    private Object max(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    public Object doMax(BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.value;
        }
        return doMax(node.right);
    }

    /**
     * 存储关键字和对应的值
     *
     * @param key
     * @param value
     */
    public void put(int key, Object value) {
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            parent = node;
            if (key < node.key) {
                node = node.left;
            } else if (node.key < key) {
                node = node.right;
            } else {
                //1. key 有了 更新
                node.value = value;
                return;
            }
        }
        //2. key 没有 新增
        if (parent == null) {
            root = new BSTNode(key, value);
            return;
        }
        if (key < parent.key) {
            parent.left = new BSTNode(key, value);
        } else {
            parent.right = new BSTNode(key, value);
        }
    }

    /**
     * 查找关键字的后任值
     *
     * @param key
     * @return
     */
    public Object successor(int key) {
        BSTNode p = root;
        BSTNode ancestorFormRight = null;
        while (p != null) {
            if (key < p.key) {
                ancestorFormRight = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        /*
            找到节点
                情况1:节点有右子树,此时后任就是左子树的最大值
                情况2:节点没有右子树,若离它最近的,自左而来的祖先就是前任
         */
        //情况1:节点有左子树,此时前任就是左子树的最大值
        if (p.right != null) {
            return min(p.right);
        }
//        情况2:节点没有左子树,若离它最近的,自右而来的祖先就是前任
        return ancestorFormRight != null ?
                ancestorFormRight.value : null;
    }

    /**
     * 查找关键字的前任值
     *
     * @param key
     * @return
     */
    public Object predecessor(int key) {
        BSTNode p = root;
        BSTNode ancestorFormLeft = null;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (p.key < key) {
                ancestorFormLeft = p;
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        /*
            找到节点
                情况1:节点有左子树,此时前任就是左子树的最大值
                情况2:节点没有左子树,若离它最近的,自左而来的祖先就是前任
         */
        //情况1:节点有左子树,此时前任就是左子树的最大值
        if (p.left != null) {
            return max(p.left);
        }
//        情况2:节点没有左子树,若离它最近的,自左而来的祖先就是前任
        return ancestorFormLeft != null ?
                ancestorFormLeft.value : null;
    }

    /**
     * 根据关键字删除
     *
     * @param key
     * @return
     */
    public Object delete(int key) {
        BSTNode p = root;
        BSTNode parent = null;
        while (p != null) {
            if (key < p.key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        //执行删除操作
        if (p.left == null) {
            //情况1:删除节点没有左节点
            shift(parent, p, p.right);
        } else if (p.right == null) {
            //情况2:删除节点没有右节点
            shift(parent, p, p.left);
        } else {
            //情况4:(此时说明被删除节点既有左子树,又有右子树)
            //4.1、找到被删除节点的后继节点
            BSTNode s = p.right;
            BSTNode sParent = p;//后继父亲
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            //后继节点即为s
            if (sParent != p) {
                //不相邻
                //4.2、处理后继的后事
                shift(sParent, s, s.right);//不可能有左孩子
                s.right = p.right;
            }
            //4.3、后继取代被删除节点
            shift(parent, p, s);
            s.left = p.left;
        }
        return p.value;
    }

    /**
     * 托孤方法
     * @param parent 被删除节点的父亲
     * @param deleted 本删除节点
     * @param child 被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            root = child;
        } else if (deleted == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

//    public Object get(int key) {
//        return doGet(root,key);
//    }

    private Object doGet(BSTNode node, int key) {
        if (node == null) {
            return null; //没找到
        }
        if (key < node.key) {
            return doGet(node.left, key);
        } else if (node.key < key) {
            return doGet(node.right, key);
        } else {
            return node.value;
        }
    }

    //非递归实现
    public Object get1(int key) {
        BSTNode node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (node.key < key) {
                node = node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }

    static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
